Solution

A statement in mathematical logic is a declarative sentence which has a definite truth value, either true or false.

$(i)$ There will be snow in January.
This is a declarative sentence. So, it is a statement.

$(ii)$ What is the time now?
This is a question. So, it is not a statement.

$(iii)$ Today is Sunday.
This is a declarative sentence. So, it is a statement.

$(iv)$ You must study Discrete Mathematics.
This is a command or advice. So, it is not a statement.

Therefore, only $(i)$ and $(iii)$ are statements.

Solution

Equivalence is represented by

$p\Leftrightarrow q$

So,

$(a)\rightarrow(iv)$

Contrapositive of $p\Rightarrow q$ is

$\sim q\Rightarrow \sim p$

So,

$(b)\rightarrow(iii)$

Converse of $p\Rightarrow q$ is

$q\Rightarrow p$

So,

$(c)\rightarrow(ii)$

Implication is represented by

$p\Rightarrow q$

So,

$(d)\rightarrow(i)$

Therefore, correct matching is

$(a)-(iv),\ (b)-(iii),\ (c)-(ii),\ (d)-(i)$

Solution

Total balls are

$6+4=10$

Number of ways to select $4$ balls from $10$ balls is

${}^{10}C_4$

We need exactly $2$ red balls and $2$ green balls.

Number of ways to select $2$ red balls from $6$ red balls is

${}^{6}C_2$

Number of ways to select $2$ green balls from $4$ green balls is

${}^{4}C_2$

So, required probability is

$\dfrac{{}^{6}C_2 \times {}^{4}C_2}{{}^{10}C_4}$

$=\dfrac{15 \times 6}{210}$

$=\dfrac{90}{210}$

$=\dfrac{3}{7}$

Solution

Let Bus, Train and Automobile be represented by $B,T,A$ respectively.

Given,

$n(B)=30$

$n(T)=35$

$n(A)=100$

$n(B\cap T)=15$

$n(B\cap A)=15$

$n(T\cap A)=20$

$n(B\cap T\cap A)=5$

Using the formula,

$n(B\cup T\cup A)=n(B)+n(T)+n(A)-n(B\cap T)-n(B\cap A)-n(T\cap A)+n(B\cap T\cap A)$

Now,

$n(B\cup T\cup A)=30+35+100-15-15-20+5$

$=165-50+5$

$=120$

Therefore, $120$ people completed the survey form.

Solution

Statement $(i)$ is true.

NAND and NOR gates are functionally complete gates.

So, every logic network can be represented using only NAND gates or only NOR gates.

Statement $(ii)$ is true.

Boolean expressions and logic networks can be represented using labelled acyclic digraphs.

Statement $(iii)$ is false.

Any two Boolean algebras with the same number of atoms are isomorphic.

Statement $(iv)$ is false.

In a finite Boolean algebra, every non-zero element can be uniquely expressed as a join of atoms.

Therefore, only $(i)$ and $(ii)$ are true.

Solution

Solution

Given Boolean expression is

$\overline{A}\cdot B+A\cdot \overline{B}+A\cdot B$

Now, group the last two terms:

$= \overline{A}\cdot B+A(\overline{B}+B)$

Since,

$\overline{B}+B=1$

So,

$= \overline{A}\cdot B+A$

Using Boolean identity,

$A+\overline{A}B=A+B$

Therefore,

$\overline{A}\cdot B+A\cdot \overline{B}+A\cdot B=A+B$

Solution

In PERT/CPM network, a merge event is an event where two or more activities come together.

It represents the joining of two or more events or activities.

Therefore, the merge event represents joining.

Solution

Given objective function is

$z=-2x_1-3x_2$

To maximize $z=-2x_1-3x_2$, we need to minimize the negative loss.

The main lower constraint is

$x_1+x_2\geq 2$

Now check the feasible corner points on $x_1+x_2=2$:

If $x_2=0$, then

$x_1=2$

So, point is $(2,0)$.

At $(2,0)$,

$z=-2(2)-3(0)$

$z=-4$

If $x_1=0$, then

$x_2=2$

So, point is $(0,2)$.

At $(0,2)$,

$z=-2(0)-3(2)$

$z=-6$

Since $-4>-6$, maximum value is $-4$.

Also, $(2,0)$ satisfies the other constraints:

$2x_1+x_2=2(2)+0=4\leq 10$

$x_1+x_2=2+0=2\leq 8$

Therefore, optimal solution is

$x_1=2,\ x_2=0,\ z=-4$

Solution

In computers, subtraction is generally performed using $2$'s complement method.

For subtracting $B$ from $A$, the computer takes the $2$'s complement of $B$ and adds it to $A$.

This makes subtraction possible using the same binary adder circuit used for addition.

Therefore, subtraction in computers is generally carried out by $2$'s complement.

Solution

For equation $(i)$,

$wx+w(\overline{x}+y)+x(\overline{x}+y)$

$=wx+w\overline{x}+wy+x\overline{x}+xy$

Since,

$x\overline{x}=0$

So,

$=wx+w\overline{x}+wy+xy$

$=w(x+\overline{x})+wy+xy$

$=w+wy+xy$

$=w+xy$

But the right side is

$x+wy$

Since $w+xy$ is not always equal to $x+wy$, equation $(i)$ is false.

Now, for equation $(ii)$,

$(w\overline{x}(y+x\overline{z})+\overline{w}\overline{x})y$

$=(w\overline{x}y+w\overline{x}x\overline{z}+\overline{w}\overline{x})y$

Since,

$\overline{x}x=0$

So,

$=(w\overline{x}y+\overline{w}\overline{x})y$

$=w\overline{x}y+\overline{w}\overline{x}y$

$=\overline{x}y(w+\overline{w})$

$=\overline{x}y$

So, equation $(ii)$ is true.

Therefore, $(i)$ is false and $(ii)$ is true.

Solution

Using Kruskal's algorithm, we select edges in increasing order of weights, without forming a cycle.

From the graph, the selected edge weights are:

$1,1,1,2,2,2,3,4$

Since the graph has $9$ vertices, the minimum spanning tree must have

$9-1=8$ edges.

Now, total weight of MST is

$1+1+1+2+2+2+3+4$

$=16$

Therefore, the weight of the minimum spanning tree is

$16$

Solution

Statement $(i)$ is false.

Self-relocating code is mainly supported by relative addressing, not by auto increment addressing.

Statement $(ii)$ is false.

Auto increment addressing does not necessarily require an additional ALU. The increment can be handled by the processor hardware.

Statement $(iii)$ is true.

In auto increment addressing mode, the register is incremented according to the size of the data item accessed.

For example, if byte is accessed, increment may be $1$. If word is accessed, increment may be more.

Therefore, only statement $(iii)$ is true.

Solution

Memory size is

$256K=256\times 1024=2^8\times 2^{10}=2^{18}$ words

So, address part requires

$18$ bits

Number of registers is

$64=2^6$

So, register code requires

$6$ bits

Instruction size is

$32$ bits

Indirect bit requires

$1$ bit

So, operation code bits are

$32-1-6-18=7$

Therefore, operation code, register code and address part are

$7,6,18$

Solution

Given,

$AL=153$

Binary form of $153$ is

$10011001$

The instruction NEG AL performs two's complement.

So,

Two's complement of $10011001$ is

$01100111$

Therefore,

$AL=01100111$

Since the operand is non-zero, Carry Flag is set.

So,

$CF=1$

The result $01100111$ has most significant bit $0$.

So, Sign Flag is

$SF=0$

Solution

Given number is

$-40.1$

Since the number is negative, sign bit is

$1$

Now,

$40.1$ in binary is approximately

$101000.000110011001100110\ldots$

Normalize it:

$101000.000110011001100110\ldots=1.01000000110011001100110\ldots\times 2^5$

So, exponent is

$5$

IEEE-754 single precision bias is

$127$

Biased exponent is

$127+5=132$

Binary of $132$ is

$10000100$

Mantissa bits are

$01000000110011001100110$

So, IEEE-754 representation is

$1\ 10000100\ 01000000110011001100110$

This gives hexadecimal form:

$\text{C2206666}$

Therefore, the answer is

$\text{0xC2206666}$

Hence, the correct answer is Option 1.

Solution

Gate $1$ is a NAND gate with inputs $A$ and $B$.

So, output of gate $1$ is

$\overline{AB}$

Now, gate $2$ is a NOR gate.

Its inputs are $\overline{A}$ and $B$.

So, output of gate $2$ is

$\overline{\overline{A}+B}$

Using De Morgan's law,

$\overline{\overline{A}+B}=A\overline{B}$

Now, gate $3$ is also a NOR gate.

Its inputs are $\overline{AB}$ and $A\overline{B}$.

So,

$Y=\overline{\overline{AB}+A\overline{B}}$

Now,

$\overline{AB}=\overline{A}+\overline{B}$

Therefore,

$Y=\overline{\overline{A}+\overline{B}+A\overline{B}}$

Since $\overline{B}+A\overline{B}=\overline{B}$,

$Y=\overline{\overline{A}+\overline{B}}$

Using De Morgan's law,

$Y=AB$

Solution

Number of surfaces is

$32=2^5$

So, surface number needs $5$ bits.

Number of tracks is

$64=2^6$

So, track number needs $6$ bits.

Number of sectors is

$512=2^9$

So, sector number needs $9$ bits.

Therefore, total bits required are

$5+6+9=20$

Solution

evel $1$ hit rate $=0.7$

Level $2$ hit rate $=0.8$

Level $1$ access time $=0.5$ ns

Level $2$ access time $=5$ ns

Main memory access time $=100$ ns

Average access time is

$0.7(0.5)+0.3[0.8(5)+0.2(100)]$

$=0.35+0.3[4+20]$

$=0.35+0.3(24)$

$=0.35+7.2$

$=7.55$ ns

Solution

Statement $(i)$ is not a standard sufficient condition for Hamiltonian graph.

By Dirac's theorem, the sufficient condition is

$\deg(v)\geq \dfrac{n}{2}$

for every vertex $v$.

So, statement $(i)$ is false.

Statement $(ii)$ is true by Ore's theorem.

Ore's theorem says that if for every pair of non-adjacent vertices $v$ and $w$,

$\deg(v)+\deg(w)\geq n$

then the graph is Hamiltonian.

Statement $(iii)$ is not the standard sufficient condition here.

Therefore, only statement $(ii)$ is correct.

Solution

Given,

$T(n)=2T(\sqrt{n})+\lg n$

Let

$n=2^m$

So,

$\lg n=m$

and

$\sqrt{n}=2^{m/2}$

Let

$S(m)=T(2^m)$

Then,

$S(m)=2S\left(\dfrac{m}{2}\right)+m$

Using Master theorem,

$a=2,\ b=2$

So,

$m^{\log_b a}=m^{\log_2 2}=m$

Therefore,

$S(m)=O(m\lg m)$

Now put back $m=\lg n$.

So,

$T(n)=O(\lg n\lg(\lg n))$

Solution

Insert elements one by one into max-heap.

After inserting $42,25,30$:

$\langle 42,25,30\rangle$

Insert $40$.

Since $40>25$, swap them:

$\langle 42,40,30,25\rangle$

Insert $22$:

$\langle 42,40,30,25,22\rangle$

Insert $35$.

Since $35>30$, swap them:

$\langle 42,40,35,25,22,30\rangle$

Insert $26$.

No swap is needed.

Final max-heap array is

$\langle 42,40,35,25,22,30,26\rangle$

Solution

Given sequences are

$X=\langle 0,1,2,1,3,0,1\rangle$

$Y=\langle 1,3,2,0,1,0\rangle$

One longest common subsequence is

$\langle 1,2,1,0\rangle$

This subsequence has length

$4$

Therefore, the length of the longest common subsequence is

$4$